package jjn.round1;

import commons.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jjn
 * @since 2022/9/26 00:01
 */
public class LeetCode257_BinaryTreePaths {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        backtrack(result, root, new ArrayList<>());
        return result;
    }

    private void backtrack(List<String> result, TreeNode node, List<String> path) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            path.add(String.valueOf(node.val));
            if (path.size() > 1) {
                result.add(String.join("->", path));
            } else {
                result.add(path.get(0));
            }
            path.remove(path.size() - 1);
            return;
        }
        path.add(String.valueOf(node.val));
        backtrack(result, node.left, path);
        backtrack(result, node.right, path);
        path.remove(path.size() - 1);
    }
}
